1. Field of the Invention
The present invention relates generally to an apparatus and method for a broadcast encryption. More particularly, the present invention relates to an apparatus and method for efficiently generating a key for a broadcast encryption.
2. Description of the Related Art
Typically, encryption systems are categorized based on an encryption key management into a symmetric key (or a secret key) encryption system and an asymmetric key (or a public key) encryption system. The symmetric key encryption system, which was primarily used before the public key encryption system was introduced, uses the same key for the encryption and the decryption. For instance, given that a sender encrypts a text message using an encryption key and an encryption algorithm and sends the encrypted message to a receiver, the receiver decrypts the message to obtain the original message using the same encryption key and an encryption algorithm.
The receiver needs to securely exchange the encryption key before cryptographic communications. A third party, who attempts to illegally listen to the cryptographic communications, is not able to obtain the original text message without the encryption key used by the sender and the receiver. However, the greater the number of counterparts that there are in relation to the key management and the encryption, the greater the number of keys there are to be managed. Thus, the key management and the key exchange become problematic.
In contrast, the asymmetric encryption system is based on a mathematical function, and uses a pair of keys, unlike the symmetric encryption system. One of the keys can be obtained and shared by anyone, and the other key is kept secure to one who has the encryption key. The open key is referred to a public key and the key kept secure is referred to as a private key.
For cryptographic communications between the sender and the receiver using the public key, the sender first encrypts and sends a message using the public key of the receiver, and the receiver decrypts the encrypted message using its private key to obtain the original message. Even if someone obtains the encrypted message over the network, it is impossible to decrypt the encrypted message. Thus, the message can be delivered securely. As only an authorized person keeps the private key, the private key is not provided or known to others.
The symmetric key is prevalently used to encrypt and decrypt a broadcast stream. This is because the symmetric key facilitates quite rapid encryption and decryption and is securely exchangeable through a limited access system being accessible only by an authorized user among designated users.
FIG. 1 depicts a network structure of a data transmission system according to a related art broadcast encryption. In FIG. 1, a content creator 100 creates diverse available data including audio data or video data and provides the created data to a service provider 110. The service provider 110 broadcasts the received data to trusted users who pay for the relevant data via a variety of wired or wireless communication networks, for example, broadcasts to a mobile digital rights management (DRM) network 140 and a smart home DRM network 150.
The service provider 110 can transmit data via a satellite 120 to users' devices such as a set-top box 141 that is provided with a satellite receiver, or to a mobile terminal 142 over a mobile communication network. Furthermore, the service provider 110 can transmit data to terminals 150, 151, 152, 153, 154, and 155 in the smart home network 150 via an Internet network 130.
Data is encrypted according to a broadcast encryption (BE) to prevent a piratical user 160 who does not pay for the relevant data from obtaining the data.
The security of the encryption and the decryption depends on a system being in charge of the encryption key management. A great concern in the encryption key management system is key generation. In addition, the management and the update of the created encryption key are also crucial.
FIG. 2 depicts a comparison between the public key algorithm 210 and the BE algorithm 220. Referring to FIG. 2, according to the public key algorithm 210, data including a key for trusted users is transmitted. Specifically, data that the service provider 230 transmits via a broadcast and home network 200 consists of a header 250 and encrypted data 260. The header 250 contains authentication information, and the encrypted data 260 includes actual data information. The header 250 includes a group ID 251 and keys 252, 253, 254, and 255 of authenticated users 281, 282, 283, and 284 in an authenticated group 280 so that the data can be delivered only to the users in the authenticated group 280 among a plurality of users 280, 290 and 291. When the service provider 230 encrypts and transmits the data according to Certificate Revocation List (CRL)/Online Certificate Status Protocol (OCSP) 240, a user receiving the data checks its key information included in the data header 250, normally obtains the authentication, and then utilizes the received data.
According to the BE algorithm 220, a header 270 includes only a group ID 271 and a key 272 of a relevant group. Thus, the trusted users 281, 282, 283, and 284 in the authenticated group 280 can decrypt the received data using their group keys.
Comparing with the public key algorithm 210, the BE algorithm 220 is characterized by the efficient data transmission owing to a relatively small size of the header 270. However, if the group key is hacked, the BE algorithm 220 has to update the keys of all trusted users within the authenticated group.
Meanwhile, U.S. Pat. No. 6,118,873 discloses a system for encrypting broadcast music, videos, and other content. As set forth therein, only authorized player-recorders can play and/or copy the content, and only in conformity with rules established by the vendor of the content. In the encryption method disclosed in the above-referenced patent, authorized player-recorders are issued software-implemented device keys from a matrix of device keys. These keys can be issued simultaneously with each other or over time. In any event, no player-recorder is supposed to have more than one device key per column of the matrix. Although two devices might share the same key from the same column, it is very rare that any two devices share, substantially, exactly the same set keys from all the columns of the matrix. The keys are used to decrypt the content.
In the case where a device (and its keys) becomes compromised deliberately or by mistake, it is necessary to revoke the keys of the device. Revoking a set of keys effectively renders the compromised device (and any clones thereof) inoperable to play content that is produced after the revocation. In the above-referenced patent, about 320 message bytes are required for each revocation. While this is effective, it is desirable to reduce the length of the revocation message even further for better efficiency.
While the system disclosed in the above-referenced patent is effective, because of size constraints of the header area of the message (referred to as “media key block” in the referenced patent), only a relatively limited (10,000 for a 3M header such as DVD-Audio) number of revocations can be made during the life of the system. This number can be increased by increasing the header size, but the added revocations would be applicable only to newly made devices, and not to devices that were made before the header size increase. It is desirable to be able to execute a large number of revocations of both “old” and “new” devices, i.e., to account for stateless receivers. Also, since more than one device can share any particular key with the compromised device in the above-referenced patented invention, revoking a set of device keys might result in revoking some keys held by innocent devices. It is desirable to further reduce the chances of accidentally revoking a “good” device, preferably to zero.
Other methods for broadcasting the encryption include those disclosed in Fiat et al., titled Broadcast Encryption, Crypto '93, LNCS vol. 839, pp. 257-270 (1994). This method envisions removing any number of receivers as long as at most “t” of them collude with each other. However, the Fiat et al. method requires relatively large message lengths, a relatively large number of keys stored at the receiver, and each receiver to perform more than a single decryption operation. Furthermore, the Fiat et al. method does not envision the stateless receiver scenario. It is required to avoid assuming a priori how many receivers might collude. Also, it is required to minimize the message size and number of stored keys and to minimize the number of decryption operations that must be performed by a receiver, thus optimizing performance.
Other encryption systems, like the Fiat et al. system, do not provide for the scenario of stateless receivers, and thus cannot be effectively applied as is to content protection of recorded media. Examples of such systems include the tree-based logical key hierarchy systems disclosed in Wallner et al., titled “Key management for Multicast: Issues and Architectures”, IETF draft wallner-key, 1997; Wong et al., titled “Secure Group Communication Using Key Graphs”, SIGCOMM 1998; Canetti et al., titled “Multicast Security: A Taxonomy and Some Efficient Constructions”, Proc. of INFOCOM '99, vol. 2, pp. 708-716 (1999); Canetti et al., titled “Efficient Communication-Storage Tradeoffs for Multicast Encryption”, Eurocrypt 1999, pp. 459-474; and McGrew et al., titled “Key Establishment in Large Dynamic Groups Using One-Way Function Trees”, submitted to IEEE Transactions on Software Engineering (1998). With more specificity regarding the methods of Wallner et al. and Wong et al., keys are assigned by assigning an independent label to each node in a binary tree.
FIG. 3 depicts a concept of the BE that assigns keys to a related art tree structure. In FIG. 3, users 32 through 47 receiving data according to the BE algorithm are provided with its unique keys and keys held by nodes being connected in the tree structure.
For example, user 34 can obtain a key of user 34, a key of a node 17, a key of a node 8, a key of a node 4, and a key of a node 2. The key of the node 17 is shared by user 34 and user 35. Likewise, the key of the node 8 is shared by the users of the keys 32, 33, 34, and 35.
If all the users 32 through 47 are trusted, it is desirable to add the key of the node 2 into a header of data ready to transfer and transmit the data to all of the users 32 through 47, to thus securely transmit the data.
If an unreliable user, that is, if a revoked user obtains the key of the user 36, it is required to update the relevant keys because the other nodes share the keys relating to the user 36. For example, it is necessary to update the keys of the node 18, the node 9, the node 4, and the node 2. The updating of the keys is conducted from a lower level to an upper level.
As the key of the node 18 is shared by user 37, the updated key of the node 18 is encrypted from a server for the key of user 37 and transmitted to user 37. Next, as the key of the node 9 is shared by the users 37, 38, and 39 below the node 19, the updated key of the node 9 is encrypted and transmitted to user 37 as the pre-updated key of the node 18. The updated key of the node 9 is encrypted and transmitted to users 38 and 39 as the key of the node 19.
In the same manner, as the key of the node 4 is shared by users 32, 33, 34, and 35 below the node 8 and users 37, 38, and 39 below the node 9, the updated key of the node 4 is encrypted and transmitted to users 32 through 35 as the key of the node 8, and to users 37, 38, and 39 as the pre-updated key of the node 9.
Finally, the key of the node 2 is shared by users 23 through 39, excluding user 36, below the node 4, and users 40 through 47 below the node 5. Accordingly, the updated key of the node 2 is encrypted and transmitted to users 32, 33, 34, 35, 37, 38, and 39 as the pre-updated key of the node 4. The updated key of the node 2 is encrypted and transmitted to users 40 through 47 as the key of the node 5. Therefore, such a key updating can block the access of the illegal or revoked user.
However, according to the related art key update method, some nodes are subjected to changes upon the occurrence of the revoked user. Even if the revokes and batches relating to the key update are carried out with respect to the whole nodes, a receiver requires at least log N times of the key decryptions and r log N times of the key transports. Given a great number of users who receive the broadcast data, the data become enormous. Herein, ‘r’ is the number of devices to be revoked, and ‘N’ is the total number of the receivers within the system. Data to be transferred for the key update is not substantially required data but overhead information that greatly decreases the substantial data transfer rate. Thus, a need arises for the more efficient key derivation, key distribution, and key update for the sake of the BE.